The present invention relates to a turbo decoding apparatus decoding data encoded by turbo-encoding.
Error correction codes are applied to systems which required to transmit data without any error in the case of transmitting the data or to read data to be stored in storages having a large capacity such as magnetic disks, CD-ROMs, etc. The error codes are applied to systems such as a mobile communication system, a facsimile (FAX), and a cash dispenser at the bank.
The turbo code is known as one of the error correction codes having a high coding gain. The turbo code is employed for the third generation mobile phone system (3GPP: the 3rd Generation Partnership Project) and is expected to be used for the next generation mobile phone system in the field of mobile communications.
FIG. 1 shows a diagram of an example of a configuration of a communication system including a turbo encoder and a turbo decoder. Information u having a length N is coded into pieces of coded data xa, xb and xc by the turbo encoder. The data xa is the information u itself, the data xb is coded data into which the information u is convolution-coded, and the data xc is coded data into which the information u is convolution-coded after interleaving. The pieces of coded data xa, xb, xc are affected by noises and fading when transmitting on a communication path and received as received signals ya, yb, yc. In a receiver, the turbo decoder executes a decoding process with respect to the reception signals (reception data), whereby a decoded result u′ is acquired from the reception signals.
The symbols shown in FIG. 1 are expressed as follows.
Information (original data) u=[u1, u2, . . . , uN]
Coded data xa=[xa1, xa2, . . . , xak, . . . , xaN]
Coded data xb=[xb1, xb2, . . . , xbk, . . . , xbN]
Coded data xc=[xc1, xc2, . . . , xck, . . . , xcN]
Reception data ya=[ya1, ya2, . . . , yak, . . . , yaN]
Reception data yb=[yb1, yb2, . . . , ybk, . . . , ybN]
Reception data yc=[yc1, yc2, . . . , yck, . . . , ycN]
Decoded result (decoded data) u′=[u′1, u′2, . . . , u′N]
FIG. 2 illustrates an example of a configuration of the turbo decoding apparatus (turbo decoder). The turbo decoding apparatus, to start with, uses a first component decoder DEC 1 in order to decode the reception signals ya, yb among the reception signals ya, yb and yc. Next, a second component decoder DEC 2 executes the decoding process by using a likelihood of a decoded result of the DEC 1 and using the reception signal yc. On this occasion, the likelihood of the decoded result of the DEC 1 is subjected to an interleaving process by an interleaver and input to the DEC 2. A likelihood of the decoded result of the DEC 2 is subjected to a deinterleaving process by a deinterleaver and input again to the DEC 1. The decoded result u′ is decoded data obtained by 0-or-1 determination with respect to the deinterleaved result of the DEC 2. A characteristic of an error rate is improved by repeating the decoding process. Therefore, the turbo decoding apparatus executes the decoding process in a way that repeats the decoding operation a predetermined number of times.
Note that FIG. 2 illustrates, in terms of explaining the principle, two pieces of component decoders (DEC 1 and DEC 2), the interleaver, and the deinterleaver as the components of the turbo decoding apparatus, however, a general scheme in terms of a hardware configuration is that one element decoder that functions as both of the interleaver and the deinterleaver is employed.
A Conventional Example 1 will be described in a turbo decoding apparatus applied to Maximum A Posteriori Probability Decoding (MAP), which is employed as a component decoder of a turbo decoding apparatus in general.
FIG. 3 shows a block diagram of a turbo decoding apparatus to which a MAP decoder is applied. A decoding procedure (sequence) using the MAP is given as below. A Random Access Memory (RAM) for communication path values) can save the reception signals ya, yb, yc and can output the reception signals in the way of properly exchanging an output order.
In FIG. 3, for example, when a coding rate R is given by R=1/2 and N is an information length, the original information u, the coded data xa, xb, and the reception signals ya, yb are as the followings.
Original Information:
u=[u1, u2, u3, . . . , uN]
Coded Data:
xa=[xa1, xa2, xa3, . . . xak, . . . , xaN]
xb=[xb1, xb2, xb3, . . . xbk . . . ,
Reception Data:
ya=[ya1, ya2, ya3, . . . , yak, . . . , yaN]
yb=[yb1, yb2, yb3, . . . ybk . . . , .
Note that the information length N includes a tail bit added on the side of the turbo encoder.
In FIG. 3, a shift-probability calculation unit, when receiving the reception data (yak,ybk) at time k, calculates each of the following probabilities as a shift probability γs, k (where s=0 to 3):
probability γ0, k when (xak,xbk) is (0,0);
probability γ1, k when (xak,xbk) is (0,1);
probability γ2, k when (xak,xbk) is (1,0); and
probability γ3, k when (xak,xbk) is (1,1).
A backward-probability calculation unit calculates a backward-probability βk−1(m) in each status m (m=0 to 7) at time k−1 by use of a backward-probability βk(m) and the shift-probability γs, k (s=0 to 3) at the time k, and stores the backward-probability in a backward-probability RAM (memory). Hereinafter, the shift-probability calculation unit and the backward-probability calculation unit repeat the calculations at the time k given by k=k−1, then calculate the probabilities with respect to the time k=N through k=0, and stores the backward-probability βk(m) corresponding to each of the times k=0 through N in the backward-probability RAM.
Thereafter, the shift-probability calculation unit and a forward-probability calculation unit calculate a forward-probability a1,k with the original data uk being “1” and a forward-probability a0,k(m) with the original data uk(m) being “0” in each status m at the time k by use of a forward-probability a1,k−1(m) with the original data uk−1 being “1”, a forward-probability a0,k−1(m) with the original data uk−1 being “0”, and a shift-probability γs,k at the time (k−1).
A joint-probability calculation unit calculates a probability γ1,k(m) with the k-th original data uk being “1” in a way that multiplies a forward-probability a1,k(m) in each status m at the time k by the backward-probability βk(m) stored in the backward-probability RAM. Similarly, the joint-probability calculation unit calculates a probability γ0,k(m) with the original data uk being “0” by use of the forward-probability a0,k(m) in each status m at the time k and the backward-probability βk(m).
The a posteriori probability calculation unit obtains both of a total sum Smγ1,k(m) of the probabilities that are “1” by adding the probabilities γ1,k(m) that are “1” in each status m at the time k and a total sum Smγ0,k(m) of the probabilities that are “0” by adding the probabilities γ0,k(m) that are “0” in each status m at the time k, and outputs a logarithmic likelihood (a posteriori probability L(u1k)) given by the following formula (1):L(u1k)=log[Smγ1,k(m)/Smγ0,k(m)]  (1)
An external information likelihood calculation unit, with the a posteriori probability L(u1k) containing an a priori likelihood and a communication path value at time of inputting, removes these values and thus calculates an external information likelihood Le(u1k). The external information likelihood Le(u1k) is stored in an interleave RAM, then is interleaved, subsequently is output as an a priori likelihood L(u1k′) in a next decoding process, and is fed back to the shift-probability calculation unit.
The first half of the decoding process (single MAP decoding process) of the turbo decoding is finished in the way described above, next what the reception data ya interleaved and the a priori likelihood L(u1k′) acquired in the first half of the decoding process are deemed as reception data ya′, and the MAP decoding process is executed by using ya′ and yc, thereby outputting a likelihood L(u2k). Thus, one turbo decoding process is terminated. Hereinafter, the turbo decoding process is repeated a predetermined number of times (e.g., 8 times), in which a decoded result uk=1 is output when the acquired posteriori probability L(u8k)>0, and a decoded result uk=0 is output when L(u8k)<0.
In this type of MAP decoding method, the first half of the decoding process involves the process of calculating the shift-probability and the backward-probability, and storing the backward-probability β in the backward-probability RAM, and the second half of the process involves calculating the shift-probability, the forward-probability, the joint-probability, the a posteriori-probability, and the external information likelihood. Namely, in this decoding method, the backward-probability RAM (memory) is stored with the backward-probability βk(m) without storing the forward-probabilities a1,k(m), a0,k(m).
In other words, the processes are as the followings.
(1) Calculation of shift-probability
The shift-probabilities γs,k is obtained from the reception data (yak, ybk) received at the time k, with respect to all of combinations of the case where each piece of coded data (xa, xb) becomes “0” and the case where the coded data (xa, xb) becomes “1”. The calculation of the shift-probability is performed respectively at the time of (2) the calculation of the backward-probability and (3) the calculation of the forward-probability that follow.
(2) Calculation of Backward-Probability
Calculations of the backward-probabilities at the time N through the time 0 are sequentially conducted. The backward-probability βk (i.e., β0,k, β1,k) at the time k is calculated from an backward-probability βk+1 at the time k+1 and a shift-probability at the time k+1, and results thereof are stored in the memory (backward-probability RAM) stored with the calculated results of the backward-probability.
(3) Calculation of Forward-Probability
Calculations of the forward-probabilities at the time 0through the time N are sequentially performed. The forward-probability a0,k when the data is “0” at the time k and the forward-probability a1,k when the data is “1” at the time k are calculated from the forward-probability a0,k−1 when the data is “0” at the time k−i, the forward-probability a1,k−1 when the data is “1”, and the shift-probability γs,k at the time k.
(4) Calculation of Joint (Binding) Probability
A calculation of the joint-probability is executed simultaneously with (3) the calculation of the forward-probability. Probabilities when each status is “0” at the time k is calculated from a0,k and β0,k, and probabilities when each status is “1” is calculated from a1,k and β1,k.
(5) Calculation of Posteriori Probability
The a posteriori probability uk and the likelihood of uk are calculated by adding the probabilities when each status is “1” at the time k and adding the probabilities when each status is “0”.
(6) Calculation of External Information Likelihood
The a posteriori probability calculation result uk at the time k contains the a priori likelihood and the communication path value when inputting, and hence these values are removed.
Decoding time (MAP decoding time) in the case of performing the calculations (1) to (6) once as the MAP decoding process is 2N. One turbo decoding process is completed with two MAP decoding processes. Hence, the processing time for one turbo decoding process becomes 4N, and, if a repetition count of the turbo decoding process is “8”, the turbo decoding process time becomes 32N.
FIG. 4 shows a timing chart of the single MAP decoding process. In this case, a memory capacity for storing the backward-probability calculation results βk is required to all of nodes N.
Next, a Conventional Example 2 will be described. The system of the Conventional Example 1 has the large memory capacity for storing the backward-probability calculation results and is therefore not suited to implementation of the circuit if as it is. Therefore, a method of reducing the memory capacity for storing the backward-probability calculation results is proposed (e.g., Patent Document 1). FIG. 5 shows a timing chart per MAP decoding process based on a system in the Conventional Example 2.
The decoding procedure of the method according to the Conventional Example 2 described in the Patent Document 1 has the following differences in the comparison with the Conventional Example 1.
(1) The information length N is segmented by a predetermined length Linto a plurality of blocks, and the decoding is conducted in every segment Ldefined as a basic unit. In this case, the information length N (time segments (section) 0 to N) is segmented into segments 0 to L1, L1 to L2, L2 to L3, . . . , Lx to N.
(2) The backward-probabilities are calculated toward time from time N+Δ. At this time, in the backward-probability calculation results in the respective periods of time N through 0, the memory is stored with the backward-probability calculation results (discrete β) in periods of time Lx, . . . , L3, L2 for every segment Land also stored with the backward-probability calculation results (continuous β) in all periods of time L1 to 0.
(3) Thereafter, the forward-probabilities in the periods of time 0 through L1 are calculated. At this time, the backward-probability calculation results (continuous β) in the periods of time 0 through L1, which are stored in the memory, are read, and the joint-probability, the a posteriori probability, and the external information likelihood with respect to each of the periods of time 0 to L1 are calculated. Almost simultaneously with the start of calculating the forward-probabilities in the periods of time 0 to L1, the backward-probability calculation results (discrete B) in L2 are read from the memory, then the backward-probabilities in the periods of time L2 to L1 are calculated by setting the backward-probability calculation results as an initial value, and the backward-probability calculation results are stored in the memory.
(4) Hereinafter, the decoding is performed in every segment Ldown to N by repeating the processes (1) to (3).
The process time in the Conventional Example 2 becomes 2N by the single MAP decoding process in the same way as in the Conventional Example 1. Hence, if the repetition count is 8, the turbo decoding process time becomes 32N.
In the Conventional Example 2, the memory capacity for storing the backward-probability calculation results is N/L+2Lin a way that takes account of avoiding a read-write access confliction to the RAM (memory) for storing the backward-probability calculation results.
Next, a Conventional Example 3 will be illustrated (e.g., Patent Document 1). The Conventional Example 3 is, unlike the Conventional Example 1, a backward-probability calculation method capable of reducing the process time and the memory capacity. The system in the Conventional Example 3, as demerits, slightly declines in terms of the characteristic of the error rate and entails implementing two pieces of backward-probability calculation units.
A decoding procedure of the method according to the Conventional Example 3 has the following differences from the Conventional Example 1. FIG. 6 shows a timing chart of one MAP decoding process in the Conventional Example 3.
(1) The information length N is segmented by a predetermined length Linto a plurality of blocks, and the decoding is conducted in every segment L defined as a basic unit. The information length N (time segments 0 to N) is segmented into segments 0 to L1, L1 to L2, L2 to L3, . . . , Lx to N.
(2) A first backward-probability calculation unit calculates the backward-probabilities in a period of the time L2 to 0. At this time, the calculation results in the period of the time L2 through the time L1 is not adopted because of its low reliability, and only the calculation results of the backward-probabilities in the time segment of L1 through 0 are stored in the RAM (memory).
(3) Next, the calculation of the forward-probabilities in the time 0 to L1 is executed, and the joint-probability, the a posteriori probability, and the external information likelihood are calculated by employing the calculation results of the forward-probabilities and the calculation results of the backward-probabilities stored in the memory.
(4) At a point of time when the first backward-probability calculation unit finishes calculating the backward-probabilities up to L1, a second backward-probability calculation unit starts calculating the backward-probabilities in the periods of time L3 through L1. The calculation of the backward-probabilities in the time segment L2 to L1 is executed in parallel with the calculation of the forward-probabilities in the time segment 0 to L1. In this case, the calculation results of the backward-probabilities in the time L3 through the time L2 are not adopted because of its low reliability, and only the calculation results of the backward-probabilities in the time segment of L2 through L1 are stored in the RAM (memory).
(5) Subsequent to calculating the forward-probabilities in the segment 0 to L1, the calculation of the forward-probabilities in the segment L1 to L2 are executed, and the joint-probability, the a posteriori probability, and the external information likelihood are calculated by employing the calculation results of the forward-probabilities and the calculation results of the backward-probabilities stored in the memory by the second backward-probability calculation unit.
(6) Hereinafter, the processes are repeated for every time segment L, and the decoding is conducted down to N.
The process time in the Conventional Example 3 becomes 2N by the single MAP decoding process in the same way as in the Conventional Example 1, and, if the repetition count is 8, the turbo decoding process time becomes 32N. In the Conventional Example 3, a capacity of the RAM (memory) for storing the calculation results of the backward-probabilities is required 2Lwhen taking into consideration the write-read access conflict.
The Conventional Examples 2 and 3 are the methods for reducing a circuit scale by reducing the memory capacity as compared with the Conventional Example 1. On the other hand, a method described in Patent Document 1 is given as a method of reducing the time required for decoding (Conventional Example 4). The system in the Conventional Example 4 is that the information length N is segmented into M-pieces of blocks, and the MAP calculation operations are executed in parallel in the respective blocks, thereby reducing the process time.
The system in the Conventional Example 4 can be applied to each of the systems in the Conventional Examples 1 to 3, and the process time when applied to each system becomes 1/M. FIG. 7 shows a timing chart in the case of applying the system of the Conventional Example 4 to the Conventional Example 2.
The Conventional Example 4 prepares the MAP decoders illustrated in FIG. 3, corresponding to a number of blocks M (MAP#1 to #M). The M-pieces of blocks are expressed such as blocks N/M, 2N/M, . . . , N(M−1)/M, N.
A first MAP decoder (MAP#1) executes the decoding process in the Conventional Example 2 with respect to the block in a segment 0 to N/M, a second MAP decoder (MAP#2) executes the decoding process in the Conventional Example 2 with respect to the block in a segment N/M to 2N/M, and MAP decoders MAP#3, . . . , #M execute the same decoding process.
Herein, each MAP decoder, when calculating the backward-probability, performs the calculation of the backward-probability by a predetermined extra amount Δ, and writes, in the backward-probability calculation results obtained after calculating the extra portions, only the calculation results of the backward-probability with respect to the last segmented data to the memory. For example, the MAP#1calculates the backward-probabilities of N/M+Δ to 0, and stores the calculation results of the backward-probabilities of L1 to 0 in the memory. The backward-probability is calculated by use of the calculation result of the backward-probability one or more times before, and hence the backward-probability β having a high reliability in the time N/M can be acquired by calculating the backward-probabilities from backward by the extra amount Δ.
When applying the Conventional Example 4, the memory capacity for storing the calculation results of the backward-probabilities is given as follows.
(1) Case of being Applied to the Conventional Example 1: N/M*M=N
(2) Case of being applied to the Conventional Example 2: N/L+2LM
(3) Case of being Applied to the Conventional Example 3: 2LM
Such a case is assumed that the turbo codes are used in a mobile phone system where the fast transmission is carried out. For example, in the case of realizing a transmission speed of 100 Mbps, it requires the decoding process of 100 M bits per second.
Herein, for example, in the case of executing the turbo decoding process by employing a 100 MHz system clock while applying the system in the Conventional Example 2, 32 seconds are needed for the data decoding per second. Accordingly, 32 pieces of turbo decoders must be implemented, resulting in an enlarged circuit scale. By contrast, the fast decoding process is executed by applying the method as in the Conventional Example 4, thereby enabling the circuit scale to be reduced by decreasing the number of the turbo decoders to be implemented. Further, the Conventional Example 1 requires the large memory capacity and is not suited to implementation of the circuit, and the Conventional Examples 2 and 3 capable of reducing the memory capacity are considered to be applied preferentially in terms of reducing the circuit scale.
[Patent Document 1] JP 2004-15285 A
[Patent Document 2] JP 3451246 A
Such a configuration is considered that the memory capacity is reduced by employing the Conventional Example 2 with no occurrence of deterioration of the characteristic of the error rate, which is seen in the Conventional Example 1, and the process time is reduced by use of the Conventional Example 4. In this case, the memory capacity needed for storing the calculation results of the backward-probabilities is given by N/L+2LM. Herein, when an M's value is increased for speeding up the process, the memory capacity approximates to an N's value in the Conventional Example 1, and an effect in reducing the memory capacity owing to the application of the Conventional Example 2 fades away. This is derived from the necessity of providing the memories, decreased in the Conventional Example 2, respectively to the plurality of MAP calculation units implemented in the Conventional Example 4. This is also applied to a case of reducing the memory capacity by adopting not the Conventional Example 2 but the Conventional Example 3.
Thus, in a combination of the Conventional Examples 2 to 3 and the Conventional Example 4, when processed at a high speed, the effect in reducing the memory capacity owing to applying the Conventional Examples 2 and 3 fades away. Therefore, this greatly affects the circuit scale of the turbo decoding device. In particular, this is a factor that hinders downsizing mobile terminal device mounted with the turbo decoder.